__author__ = 'Brandon Corfman'

from abc import ABCMeta, abstractmethod

class Stack:
  """ A container with a last-in-first-out (LIFO) queuing policy. """
  def __init__(self):
      self.list = []

  def push(self,item):
      """ Push 'item' onto the stack """
      self.list.append(item)

  def pop(self):
      """ Pop the most recently pushed item from the stack """
      return self.list.pop()

  def contains(self, item):
      return item in self.list

  def is_empty(self):
      """ Returns true if the stack is empty """
      return len(self.list) == 0


class SearchProblem:
    """
    This class outlines the structure of a search problem, but doesn't implement
    any of the methods (in object-oriented terminology: an abstract class).

    You do not need to change anything in this class, ever.
    """
    __metaclass__ = ABCMeta

    @abstractmethod
    def get_start_state(self):
        """
        Returns the start state for the search problem
        """
        pass

    @abstractmethod
    def is_goal_state(self, state):
        """
        state: Search state
        Returns True if and only if the state is a valid goal state
        """
        pass

    @abstractmethod
    def get_successors(self, state):
        """
        state: Search state

        For a given state, this should return a list of triples,
        (successor, action, stepCost), where 'successor' is a
        successor to the current state, 'action' is the action
        required to get there, and 'stepCost' is the incremental
        cost of expanding to that successor
        """
        pass

def complete_graph_search(problem, open_list):
    closed_set = set()
    goals = []
    while not open_list.is_empty():
        state, actions, cost = open_list.pop()
        if problem.is_goal_state(state):
            goals.append((state, actions, cost))
            continue
        if state not in closed_set:
            closed_set.add(state)
            for s in problem.getSuccessors((state, actions, cost)):
                if s[0] in closed_set:
                    continue
                open_list.push(s)
    return goals

def graph_search(problem, open_list):
    closed_set = set()
    while not open_list.is_empty():
        state = open_list.pop()
        if problem.is_goal_state(state):
            return True
        if state not in closed_set:
            closed_set.add(state)
            for s in problem.get_successors(state):
                if s in closed_set:
                    continue
                open_list.push(s)
    return False


def depth_first_search(problem):
    """ Search the deepest nodes in the search tree first.

    The graph search algorithm needs to return a list of actions that reaches
    the goal. """
    open_list = Stack()
    open_list.push(problem.get_start_state())
    return graph_search(problem, open_list)

def complete_depth_first_search(problem):
    """ Search the deepest nodes in the search tree first.

    The complete graph search algorithm returns a list of all state, actions, cost triples
    that reach the goal. """
    open_list = Stack()
    open_list.push(problem.get_start_state())
    return complete_graph_search(problem, open_list)

dfs = depth_first_search
complete_dfs = complete_depth_first_search